package leetcode_day._2023._12;

import general_class.TreeNode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * 2415.反转二叉树的奇数层
 * 算法：深度优先搜索、广度优先搜索
 *
 * @author yezh
 * @date 2023/12/15 13:11
 */
public class _15 {

    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, true);
        return root;
    }

    void dfs(TreeNode n1, TreeNode n2, boolean odd) {
        if (n1 != null) {
            if (odd) swap(n1, n2);
            dfs(n1.left, n2.right, !odd);
            dfs(n1.right, n2.left, !odd);
        }
    }

    void swap(TreeNode n1, TreeNode n2) {
        int tmp = n1.val;
        n1.val = n2.val;
        n2.val = tmp;
    }

    public TreeNode reverseOddLevels_bfs(TreeNode root) {
        if (root == null) return null;
        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        TreeNode node;
        boolean flag = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<TreeNode> list = new ArrayList<>(size);
            while (size-- > 0) {
                node = queue.pollFirst();
                if (node.left != null) queue.addLast(node.left);
                if (node.right != null) queue.addLast(node.right);
                list.add(node);
            }
            if (flag) {
                for (int l = 0, r = list.size() - 1; l < r; l++, r--) {
                    int tmp = list.get(l).val;
                    list.get(l).val = list.get(r).val;
                    list.get(r).val = tmp;
                }
            }
            flag = !flag;
        }
        return root;
    }

}
